// 思路：定义一个特定数组counts，根据该数组的索引来映射目标数组中的元素，最终遍历特定数组counts，得到结果

function countingSort(arr) {
    // 1. 计算序列中最大值元素和最小值元素
    let minVal = Math.min(...arr)
    let maxVal = Math.max(...arr)
    // 2. 定义计数对象counts
    let counts = new Array(maxVal - minVal + 1).fill(0)
    // 3. 统计num出现的次数
    for (let i = 0; i < arr.length; i++) {
        counts[arr[i] - minVal] += 1
    }
    // 4. 计算元素排名
    for (let i = 1; i < counts.length; i++) {
        counts[i] += counts[i - 1]
    }
    // 5. 反向填充目标数组
    let res = new Array(arr.length).fill(0)
    for (let i = arr.length - 1; i >= 0 ; i--) {
        res[counts[arr[i] - minVal] - 1] = arr[i]
        counts[arr[i] - minVal] -= 1
    }
    return res
}

// 时间复杂度为On+k， k代表待排序序列的值域
// 空间复杂度为Ok，由于用于计数的数组counts的长度取决于待排序数组中数据的范围，所以计数排序算法对于数据范围很大的数组，需要大量的内存
// 计数排序适用情况：一般用于整数排序，不适用按字母顺序，人名顺序结构
// 稳定排序

let arr = [1, 2, 7, 26, 25, 7, 19, 17, 1, 90, 3, 36]
console.log(countingSort(arr))